#include <stdlib.h>
#include <stdio.h>
// 广度优先，BFS
// 类似于树的层次遍历，需要用到队列

typedef char VertexType; // 顶点数据类型
#define MAXVEX 100       // 最大顶点数
typedef int EdgeType;  // 边的权值类型

// 图的邻接矩阵表示
typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;

int visited[MAXVEX]; // 访问标志数组, 0表示顶点未访问，1表示顶点已访问
int queue[MAXVEX]; // 辅助队列
int front = 0; // 队头指针
int rear = 0;  // 队尾指针

/*
         0 1 2 3 4 5 6 7 8
         A B C D E F G H I
    0 A  0 1 0 0 0 1 0 0 0
    1 B  1 0 1 0 0 0 1 0 1
    2 C  0 1 0 1 0 0 0 0 1
    3 D  0 0 0 1 0 1 0 1 0
    4 E  0 0 0 1 0 1 0 1 0
    5 F  1 0 0 0 1 0 1 0 0
    6 G  0 1 0 1 0 1 0 1 0
    7 H  0 0 0 1 1 0 1 0 0
    8 I  0 1 1 1 0 0 0 0 0
*/
void createGraph(Graph *G){
    G->numVertexes = 9;
    G->numEdges = 15;
    // 初始化邻接矩阵
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';

    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            G->arc[i][j] = 0;  // 整个矩阵赋值为0
        }
    }

    // 建立边
    // A-B A-F 
    G->arc[0][1] = 1;
    G->arc[0][5] = 1;

    // B-C B-G B-I
    G->arc[1][2] = 1;  
    G->arc[1][6] = 1;
    G->arc[1][8] = 1;

    // C-D C-I
    G->arc[2][3] = 1;
    G->arc[2][8] = 1;

    // D-E D-G D-H D-I
    G->arc[3][4] = 1;
    G->arc[3][6] = 1;
    G->arc[3][7] = 1;
    G->arc[3][8] = 1;

    // E-F E-H
    G->arc[4][5] = 1;
    G->arc[4][7] = 1;

    // F-G
    G->arc[5][6] = 1;

    // G-H
    G->arc[6][7] = 1;

    for (int i = 0; i < G->numVertexes; i++){
        for (int j = 0; j < G->numVertexes; j++){
            G->arc[j][i] = G->arc[i][j]; // 无向图邻接矩阵对称
        }
    }
}

// 深度优先访问
// 深度优先类似树的前序遍历，访问一个顶点后，依次递归访问其未访问的邻接顶点
void dfs(Graph G, int i){
    visited[i] = 1; // 标记顶点已访问
    printf("%c ", G.vexs[i]); // 访问顶点

    for (int j = 0; j < G.numVertexes; j++){
        // 如果存在边且未访问，则递归访问
        if (G.arc[i][j] == 1  && visited[j] ==  0){  // 1表示有边，0表示无边
            dfs(G, j);      
        }
    }
}

void bfs(Graph G, int i){
    visited[i] = 1; // 标记顶点已访问
    printf("%c ", G.vexs[i]); // 访问顶点
   
    queue[rear++] = i; // 入队列

    while (front != rear){ // 队列不空循环
        i = queue[front++]; // 出队列
        for (int j = 0; j < G.numVertexes; j++){
            // 如果存在边且未访问，则访问该顶点并入队
            if (G.arc[i][j] == 1 && visited[j] == 0){
                printf("%c ", G.vexs[j]); // 访问顶点
                visited[j] = 1; // 标记顶点已访问
                queue[rear++] = j; // 入队列
            }
        }
    }
}

int main(){
    Graph G;
    createGraph(&G);

    // 重置访问标志数组
    for (int i = 0; i < G.numVertexes; i++){
        visited[i] = 0;
    }
    front = rear = 0; // 重置队列

    bfs(G, 0); // 从第0个顶点开始广度优先遍历

    return 0;
}